﻿#include"AVLtree.h"

//class Solution {
//public:
//    int threeSumClosest(vector<int>& nums, int target) {
//        int n = nums.size();
//        int min = 1000000;
//        for (int i = 0; i < n; i++) {
//            for (int j = i + 1; j < n; j++)
//            {
//                for (int k = j + 1; k < n; k++)
//                {
//                    int sum = nums[i] + nums[k] + nums[j];
//                    if (abs(min - target) > abs(sum - target))
//                    {
//                        min = sum;
//                    }
//                }
//            }
//        }
//        return min;
//    }
//};

//class Solution {
//public:
//    int threeSumClosest(vector<int>& nums, int target) {
//        int n = nums.size();
//        int min = 1000000;
//        sort(nums.begin(), nums.end());
//        for (int i = 0; i < n - 1; i++) {
//            int left = i + 1, right = n - 1;
//            
//            while (left < right)
//            {
//                int sum = nums[left] + nums[right] + nums[i];
//                if (abs(min - target) > abs(sum - target))min = sum;
//
//                if (sum == target)
//                    return target;
//                else if (sum > target)
//                {
//                    right--;
//                    while (left < right && nums[right] == nums[right + 1])right--;
//                }
//                else
//                {
//                    left++;
//                    while (left < right && nums[left] == nums[left - 1])left++;
//                }
//
//            }
//        }
//        return min;
//    }
//};
//
//int main()
//{
//    Solution s;
//    vector<int> v({ 10,20,30,40,50,60,70,80,90 });
//    s.threeSumClosest(v, 1);
//
//    return 0;
//}

/////////////////////////////////////////////
//map的基本使用


//class Node {
//public:
//	int val;
//	Node* next;
//	Node* random;
//
//	Node(int _val) {
//		val = _val;
//		next = NULL;
//		random = NULL;
//	}
//};
//
//class Solution {
//public:
//	Node* copyRandomList(Node* head) {
//		map<Node*, Node*>mapnode;
//		Node* copyhead = nullptr, * tail = nullptr;
//		Node* cur = head;
//		while (cur)
//		{
//			if (copyhead == nullptr)
//			{
//				tail = copyhead = new Node(cur->val);
//			}
//			else
//			{
//				tail->next = new Node(cur->val);
//				tail = tail->next;
//			}
//
//			mapnode[cur] = tail;
//
//			cur = cur->next;
//		}
//
//		cur = head;
//		Node* copy = copyhead;
//		while (cur)
//		{
//			if (cur->random == nullptr)
//				copy->random = nullptr;
//			else
//			{
//				copy->random = mapnode[cur->random];
//			}
//			cur = cur->next;
//			copy = copy->next;
//		}
//		return copyhead;
//	}
//};
//
//int main()
//{
//	map<string, string> ss({ {"水果","三个" }, {"西瓜", "两个"} });
//	auto ret= ss.insert({ "哈密瓜","五个" });
//	if (ret.second)
//		cout <<"没有找到相对应的key，所以进行插入\n" << "插入成功\n";
//	else
//		cout << "插入失败\n";
//
//	auto it = ss.begin();
//	while (it != ss.end())
//	{
//		cout << it->first << ":" << it->second << endl;
//		++it;
//	}
//
//	
//
//	return 0;
//}


////////////////////////////////////////////////////////
//自己测试AVL树


void TestAVLTree1()
{
	AVLTree<int, int> t;
	// 常规的测试⽤例
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	// 特殊的带有双旋场景的测试⽤例
	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.insert({ e, e });
	}
	t.InOrder();
	cout << t.IsBalanceTree() << endl;
}
#include<vector>
void TestAVLTree2()
{
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}
	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.insert(make_pair(e, e));
	}
	size_t end2 = clock();
	cout << "Insert:" << end2 - begin2 << endl;
	cout << t.IsBalanceTree() << endl;
	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;
}

int main()
{
	TestAVLTree2();

	return 0;
}



